package leetcode.top100;


import utils.ListNode;
import utils.ListUtil;

import java.util.Stack;

/**
 * 反转链表 ，见{@link baseclass.d_list.Code02_ReverseList}
 * @since 2019/12/12 0012 下午 11:21
 */
public class Code206_ReverseList {

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
//        node.next.next = new ListNode(3);
        ListUtil.printLinkedList(node);
        node = reverseList(node);
        ListUtil.printLinkedList(node);
    }


    private static ListNode res = new ListNode(-1);
    private static ListNode newhead = res;
    public static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)  return head;
//        return process1(head);
        process2(head);
        res.next = null;
        return newhead.next;
    }


    /**
     * 递归的本质是使用递归栈，其实本质就是对方式1的改变.
     * 迭代1：
     * @param head
     * @return
     */
    private static void process2(ListNode head){
       if(head == null){
           return;
       }
       process2(head.next);
//       System.out.println(head.val);
       res.next = head;
       res = res.next;
    }

    /**
     * 迭代2
     */
    private static ListNode process3(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        //这个p是链表的最后一个节点，一直返回给递归上层
        ListNode p = process3(head.next);

        //最后一次进入这里时，head.next.next == null 。head是倒数第二个节点。 p是head.next是最后一个节点

        //反转
        head.next.next = head;
        head.next = null;

        //一直返回给上层，最后一个节点
        return p;


    }
    //方式2：迭代版
    private static ListNode process1(ListNode head){
        ListNode pre = null;
        ListNode next;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }


    //方式1：使用辅助栈。超内存限制
    private ListNode process0(ListNode head){
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while(cur != null){
            stack.push(cur);
            cur =cur.next;
        }
        head = cur = stack.pop();
        while(!stack.isEmpty()){
            cur.next = stack.pop();
            cur = cur.next;
        }
        return head;
    }
}
